Modern technology allows moving object data to be collected easily and extensively. Applications that deal with moving object data (e.g., traffic monitoring, flight control, and location-based advertisement and recommendation) typically require location-based services (LBS). LBS involve querying for the historical, current, or predicted future locations of moving objects.